﻿#pragma once
#include "Index.h"
/**
 * 航班预定统计
 * https://leetcode.cn/problems/corporate-flight-bookings/
 * 数组 前缀和 差分
 * 这里有 n 个航班，它们分别从 1 到 n 进行编号。
 * 有一份航班预订表 bookings ，表中第 i 条预订记录 bookings[i] = [firsti, lasti, seatsi] 
 * 意味着在从 firsti 到 lasti （包含 firsti 和 lasti ）的 每个航班 上预订了 seatsi 个座位。
 * 请你返回一个长度为 n 的数组 answer，里面的元素是每个航班预定的座位总数。
 */
class FlightBooking
{
public:
	std::vector<int> corpFlightBookings(std::vector<std::vector<int>>& bookings, int n)
	{
		if (bookings.empty() || n <= 0)
			return {};

		std::vector<int> diff(n, 0);
		for (auto& bookingInfo : bookings)
		{
			const int sta = bookingInfo[0];
			const int fin = bookingInfo[1];
			const int bookedCount = bookingInfo[2];

			diff[sta - 1] += bookedCount;
			if (fin < n)
				diff[fin] -= bookedCount;
		}

		std::vector<int> ans;
		ans.push_back(diff.front());
		for (int i = 1; i < n; ++i)
			ans.push_back(ans.back() + diff[i]);

		return ans;
	}
};


#ifdef DEV_TEST
#include <gtest/gtest.h>
TEST(FlightBookingTest, corpFlightBookings)
{
	TEST_SOLUTION1(FlightBooking, FlightBooking, &)
	{
		std::vector<int> bookings;

		constexpr int flightSize = 1000;
		constexpr int maxBookingCount = 300;
		constexpr int bookTimes = 500;

		bookings.resize(flightSize, 0);
		std::vector<std::vector<int>> bookingHistory;
		for (int i = 0; i < bookTimes; ++i)
		{
			std::vector<int> bookedFlights = TestingUtil::randOrderedInts(2, 1, flightSize);
			const int bookingCount = TestingUtil::randIntBetween(0, maxBookingCount);

			for (int flight = bookedFlights[0]; flight <= bookedFlights[1]; ++flight)
				bookings[flight - 1] += bookingCount;

			bookingHistory.push_back({ bookedFlights[0],bookedFlights[1],bookingCount });
		}

		std::vector<int> resultBookings = solution->corpFlightBookings(bookingHistory, flightSize);
		ASSERT_EQ(FormatedUtil::dumpFormated(resultBookings), FormatedUtil::dumpFormated(bookings))
			<< "bookingHistory=" << FormatedUtil::dumpFormated(bookingHistory) << std::endl;
	};
}
#endif